SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Sparse grid</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Sparse grid</span></span>

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p><b>Sparse grids</b> are numerical techniques to represent, integrate or interpolate high <a href="Dimension" title="Dimension">dimensional</a> functions. They were originally developed by the <a href="Russia" title="Russia">Russian</a> <a href="Mathematician" title="Mathematician">mathematician</a> Sergey A. Smolyak, a student of <a href="Lazar_Lyusternik" title="Lazar Lyusternik">Lazar Lyusternik</a>, and are based on a sparse tensor product construction. Computer algorithms for efficient implementations of such grids were later developed by <a href="Michael_Griebel" title="Michael Griebel">Michael Griebel</a>, <a href="Christoph_Zenger" title="Christoph Zenger">Christoph Zenger</a>, and Dirk Pflüger.

</p>

<div class="mw-heading mw-heading2"><h2 id="Curse_of_dimensionality">Curse of dimensionality</h2></div>

<p>The standard way of representing multidimensional functions are tensor or full grids. The number of basis functions or nodes (grid points) that have to be stored and processed <a href="Exponential_function" title="Exponential function">depend exponentially</a> on the number of dimensions.

</p><p>The <a href="Curse_of_dimensionality" title="Curse of dimensionality">curse of dimensionality</a> is expressed in the order of the integration error that is made by a quadrature of level <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math></span><img src="./829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"></span>, with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{l}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{l}}</annotation>

</semantics>

</math></span><img src="./571866e3b0d26d5062cb02156e70ce35189137e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.589ex; height:2.509ex;" alt="{\displaystyle N_{l}}" loading="lazy"></span> points. The function has regularity <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math></span><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"></span>, i.e. is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math></span><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"></span> times differentiable. The number of dimensions is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math></span><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"></span>.

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |E_{l}|=O(N_{l}^{-{\frac {r}{d}}})}">

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<mfrac>

</mfrac>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |E_{l}|=O(N_{l}^{-{\frac {r}{d}}})}</annotation>

</semantics>

</math></span><img src="./e1dfeeeaf9951dd4496a924e9b968dbc1d3f5e10.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:15.58ex; height:4.509ex;" alt="{\displaystyle |E_{l}|=O(N_{l}^{-{\frac {r}{d}}})}" loading="lazy"></span>

</p>

<div class="mw-heading mw-heading2"><h2 id="Smolyak's_quadrature_rule">Smolyak's quadrature rule</h2></div>

<p>Smolyak found a computationally more efficient method of integrating multidimensional functions based on a <a href="Univariate" title="Univariate">univariate</a> quadrature rule <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q^{(1)}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q^{(1)}}</annotation>

</semantics>

</math></span><img src="./b1c341472fab453f311462c6a4ac7d5377ce4fc5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.172ex; height:3.176ex;" alt="{\displaystyle Q^{(1)}}" loading="lazy"></span>. The <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math></span><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"></span>-dimensional Smolyak integral <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q^{(d)}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q^{(d)}}</annotation>

</semantics>

</math></span><img src="./f981960d22f4921672240f0fb81c3350fb433295.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.21ex; height:3.176ex;" alt="{\displaystyle Q^{(d)}}" loading="lazy"></span> of a function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> can be written as a recursion formula with the <a href="Tensor_product" title="Tensor product">tensor product</a>.

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{l}^{(d)}f=\left(\sum _{i=1}^{l}\left(Q_{i}^{(1)}-Q_{i-1}^{(1)}\right)\otimes Q_{l-i+1}^{(d-1)}\right)f}">

</mrow>

</mrow>

</msubsup>

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<mrow>

<mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{l}^{(d)}f=\left(\sum _{i=1}^{l}\left(Q_{i}^{(1)}-Q_{i-1}^{(1)}\right)\otimes Q_{l-i+1}^{(d-1)}\right)f}</annotation>

</semantics>

</math></span><img src="./912cc3f0122a6a17d56503847864e4c1eeb7c0c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:41.55ex; height:7.509ex;" alt="{\displaystyle Q_{l}^{(d)}f=\left(\sum _{i=1}^{l}\left(Q_{i}^{(1)}-Q_{i-1}^{(1)}\right)\otimes Q_{l-i+1}^{(d-1)}\right)f}" loading="lazy"></span>

</p><p>The index to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q}</annotation>

</semantics>

</math></span><img src="./8752c7023b4b3286800fe3238271bbca681219ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.838ex; height:2.509ex;" alt="{\displaystyle Q}" loading="lazy"></span> is the level of the <a href="Discretization" title="Discretization">discretization</a>. If a 1-dimension integration on level <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span> is computed by the evaluation of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(2^{i})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(2^{i})}</annotation>

</semantics>

</math></span><img src="./22d0807edc056a75f0f2d6feca9c19d5184caf01.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.545ex; height:3.176ex;" alt="{\displaystyle O(2^{i})}" loading="lazy"></span> points, the error estimate for a function of regularity <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math></span><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"></span> will be

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</msubsup>

<msup>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |E_{l}|=O\left(N_{l}^{-r}\left(\log N_{l}\right)^{(d-1)(r+1)}\right)}</annotation>

</semantics>

</math></span><img src="./4e9c6046493d5e7548369fb0bd2f32cb570fb71f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:32.491ex; height:4.843ex;" alt="{\displaystyle |E_{l}|=O\left(N_{l}^{-r}\left(\log N_{l}\right)^{(d-1)(r+1)}\right)}" loading="lazy"></span>

</p>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFPflügerPeherstorferBungartz2010" class="citation journal cs1">Pflüger, D.; Peherstorfer, B.; Bungartz, H. (2010). <a rel="nofollow" class="external text" href="https://www.zora.uzh.ch/id/eprint/142226/1/Scheidegger_Econometrica%24ECTA12216.pdf">"Spatially adaptive sparse grids for high-dimensional data-driven problems"</a> <span class="cs1-format">(PDF)</span>. <i>Journal of Complexity</i>. <b>26</b> (5): <span class="nowrap">508–</span>522. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jco.2010.04.001">10.1016/j.jco.2010.04.001</a>.</cite></li>

<li><cite id="CITEREFBrummScheidegger2017" class="citation journal cs1">Brumm, J.; Scheidegger, S. (2017). <a rel="nofollow" class="external text" href="https://www.zora.uzh.ch/id/eprint/142226/1/Scheidegger_Econometrica%24ECTA12216.pdf">"Using Adaptive Sparse Grids to Solve High-Dimensional Dynamic Models"</a> <span class="cs1-format">(PDF)</span>. <i><a href="Econometrica" title="Econometrica">Econometrica</a></i>. <b>85</b> (5): <span class="nowrap">1575–</span>1612. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.3982%2FECTA12216">10.3982/ECTA12216</a>.</cite></li>

<li><cite id="CITEREFGarcke2012" class="citation book cs1">Garcke, Jochen (2012). <a rel="nofollow" class="external text" href="https://ins.uni-bonn.de/media/public/publication-media/sparse_grids_nutshell_code.pdf">"Sparse Grids in a Nutshell"</a> <span class="cs1-format">(PDF)</span>. In Garcke, Jochen; <a href="Michael_Griebel" title="Michael Griebel">Griebel, Michael</a> (eds.). <i>Sparse Grids and Applications</i>. Springer. pp. <span class="nowrap">57–</span>80. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-31702-6</bdi>.</cite></li>

<li><cite id="CITEREFZenger1991" class="citation book cs1">Zenger, Christoph (1991). <a rel="nofollow" class="external text" href="https://www5.in.tum.de/pub/zenger91sg.pdf">"Sparse Grids"</a> <span class="cs1-format">(PDF)</span>. In Hackbusch, Wolfgang (ed.). <i>Parallel Algorithms for Partial Differential Equations</i>. Vieweg. pp. <span class="nowrap">241–</span>251. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-528-07631-3</bdi>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://www.lrr.in.tum.de/~murarasu/ppopp027s-murarasu.pdf">A memory efficient data structure for regular sparse grids</a></li>

<li><a rel="nofollow" class="external text" href="http://wissrech.iam.uni-bonn.de/research/projects/zumbusch/fd.html">Finite difference scheme on sparse grids</a></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20120219044130/http://cumbia.informatik.uni-stuttgart.de/ger/research/fields/recent/sparse/">Visualization on sparse grids</a></li>

<li><a rel="nofollow" class="external text" href="http://wissrech.iam.uni-bonn.de/research/pub/garcke/kdd.pdf">Datamining on sparse grids, J.Garcke, M.Griebel (pdf)</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox-body{font-style:italic}.mw-parser-output .asbox-note{font-size:smaller}.mw-parser-output .asbox .navbar{position:absolute;top:-0.75em;right:1em;display:none}.mw-parser-output :not(p):not(.asbox)+style+.asbox,.mw-parser-output :not(p):not(.asbox)+link+.asbox{margin-top:3em}

/* end https://en.wikipedia.org/ */

</style></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-03" href="https://en.wikipedia.org/wiki/?title=Sparse_grid&oldid=1293813279">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>